package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/11/19 9:39
 * @description：https://leetcode-cn.com/problems/integer-replacement/
 */
public class 整数替换 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.integerReplacement(2147483647));
    }

    /*class Solution {
        public int integerReplacement(int n) {
            if (n == 1) return 0;
            int[] dp = new int[n + 1];
            dp[1] = 0;
            dp[2] = 1;
            for (int i = 3; i <= n; i++) {
                if (i % 2 == 0) {
                    dp[i] = dp[i / 2] + 1;
                } else {
                    dp[i] = Math.min(dp[i - 1] + 1, dp[(i + 1) / 2] + 2);
                }
            }
            return dp[n];
        }
    }*/


    //递归枚举
    /*class Solution {
        public int integerReplacement(int n) {
            if (n == 1) return 0;
            if (n % 2 == 0) return integerReplacement(n / 2) + 1;
            return Math.min(integerReplacement(n / 2 + 1), integerReplacement(n / 2)) + 2;
        }
    }*/

    //记忆化搜索
    class Solution {

        private Map<Integer, Integer> map = new HashMap<>();

        public int integerReplacement(int n) {
            if (n == 1) return 0;
            if (!map.containsKey(n)) {
                int count;
                if (n % 2 == 0) {
                    count = integerReplacement(n / 2) + 1;
                } else {
                    count = Math.min(integerReplacement(n / 2)
                            , integerReplacement(n / 2 + 1))
                            + 2;
                }
                map.put(n , count);
            }
            return map.get(n);
        }
    }
}
